package hot;


/**
 * @author lakersUp
 * @Classname       实现 Tire 前缀树
 * @Description     数组套数组, 定义一个自己类型的数据结构
 * @Date 2022/3/18 10:02
 * @Version 1.0
 */
public class Hot208Trie {

    private Hot208Trie[] children;
    private boolean isEnd;

    public Hot208Trie() {
        children=new Hot208Trie[26];
        isEnd=false;

    }

    public void insert(String word) {
        Hot208Trie node=this;
        for(int i=0;i<word.length();i++){
            char ch=word.charAt(i);
            int index=ch-'a';
            if(node.children[index]==null){
                node.children[index]=new Hot208Trie();
            }
            node=node.children[index];
        }

    }

    public boolean search(String word) {
        Hot208Trie node = searchPrefix(word);
        return node!=null &&  node.isEnd;

    }

    private Hot208Trie searchPrefix(String word) {
        Hot208Trie node = this;
        for(int i=0;i<word.length();i++){
            char ch=word.charAt(i);
            int index=ch-'a';
            if(node.children[index]==null){
                return null;
            }
            node=node.children[index];
        }
        return node;

    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix)!=null;
    }
}
